package DynamicProgramming;//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 注意：给定 n 是一个正整数。 
//
// 示例 1： 
//
// 输入： 2
//输出： 2
//解释： 有两种方法可以爬到楼顶。
//1.  1 阶 + 1 阶
//2.  2 阶 
//
// 示例 2： 
//
// 输入： 3
//输出： 3
//解释： 有三种方法可以爬到楼顶。
//1.  1 阶 + 1 阶 + 1 阶
//2.  1 阶 + 2 阶
//3.  2 阶 + 1 阶
// 
// Related Topics 记忆化搜索 数学 动态规划 👍 1901 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class climbStairs1 {
    public static int climbStairs1(int n) {
        /*模拟*/
        int a=1,b=1,sum=0;
        for (int i = 0; i < n; i++) {
            sum=(a+b);
            a=b;
            b=sum;
        }
        return a;

    }
    public static int climbStairsWithout7(int n) {
        //不能爬到7及7的倍数
        /**
         * 动态规划
         * 观察问题可得，当n为1时，有1种 ，
         *          * 2时，有1，2两种
         * */
        if (n==1){
            return 1;
        }else if(n==2){
            return 2;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i=2;i<=n;i++){

            dp[i] = i%7==0 ? 0 : dp[i-1]+dp[i-2];
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];

    }
    public static int climbStairs(int n) {
        /**
         * 动态规划
         * 观察问题可得，当n为1时，有1种 ，
         * 2时，有1，2两种
         * 3,有1，1，1和1，2和2，1三种
         * 4有1，1，1，1/1,2,1/1,1,2/2,2/2,1,1 5种
         * */
        if (n==1){
            return 1;
        }else if(n==2){
            return 2;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n ; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(climbStairsWithout7(8));
        System.out.println(climbStairs(8));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
